/*
** This file contains the C functions that implement a memory allocation subsystem for use by APPID.
**
** This version of the memory allocation subsystem omits all use of malloc(). The application gives SQLite a block of memory
** before calling system_initialize() from which allocations are made and returned by the xMalloc() and xRealloc() 
** implementations. Once system_initialize() has been called, the amount of memory available to APPID is fixed and cannot
** be changed.
**
** This version of the memory allocation subsystem is included in the build only if SYSTEM_ENABLE_MEMSYS5 is defined.
**
** This memory allocator uses the following algorithm:
**
**   1.  All memory allocations sizes are rounded up to a power of 2.
**
**   2.  If two adjacent free blocks are the halves of a larger block, then the two blocks are coalesed into the single larger block.
**
**   3.  New memory is allocated from the first available free block.
**
** This algorithm is described in: J. M. Robson. "Bounds for Some Functions Concerning Dynamic Storage Allocation". Journal of the Association for
** Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499.
** 
** Let n be the size of the largest allocation divided by the minimum allocation size (after rounding all sizes up to a power of 2.)  Let M
** be the maximum amount of memory ever outstanding at one time.  Let N be the total amount of memory available for allocation.  Robson
** proved that this memory allocator will never breakdown due to  fragmentation as long as the following constraint holds:
**
**      N >=  M*(1 + log2(n)/2) - n + 1
**
** The system_status() logic tracks the maximum values of n and M so that an application can, at any time, verify this constraint.
*/
#include "System.h"

/*
** This version of the memory allocator is used only when SYSTEM_ENABLE_MEMSYS5 is defined.
*/
#ifndef SYSTEM_ENABLE_MEMSYS5

/*
** A minimum allocation is an instance of the following structure. Larger allocations are an array of these structures where the
** size of the array is a power of 2.
**
** The size of this object must be a power of two.  That fact is verified in memsys5Init().
*/
typedef struct Mem5Link Mem5Link;
struct Mem5Link
{
	int next;       /* Index of next free chunk */
	int prev;       /* Index of previous free chunk */
};

/*
** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since mem5.szAtom is always at least 8 and 32-bit integers are used,
** it is not actually possible to reach this limit.
*/
#define LOGMAX 30

/*
** Masks used for mem5.aCtrl[] elements.
*/
#define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block */
#define CTRL_FREE     0x20    /* True if not checked out */

/*
** All of the static variables used by this module are collected into a single structure named "mem5".  This is to keep the
** static variables organized and to reduce namespace pollution when this module is combined with other in the amalgamation.
*/
static SYSTEM_WSD struct Mem5Global
{
	/*
	** Memory available for allocation
	*/
	int szAtom;      /* Smallest possible allocation in bytes */
	int nBlock;      /* Number of szAtom sized blocks in zPool */
	u8 *zPool;       /* Memory available to be allocated */
  
	/*
	** Mutex to control access to the memory allocation subsystem.
	*/
	system_mutex *mutex;

	/*
	** Performance statistics
	*/
	u64 nAlloc;         /* Total number of calls to malloc */
	u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */
	u64 totalExcess;    /* Total internal fragmentation */
	u32 currentOut;     /* Current checkout, including internal fragmentation */
	u32 currentCount;   /* Current number of distinct checkouts */
	u32 maxOut;         /* Maximum instantaneous currentOut */
	u32 maxCount;       /* Maximum instantaneous currentCount */
	u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
  
	/*
	** Lists of free blocks.  aiFreelist[0] is a list of free blocks of size mem5.szAtom.  aiFreelist[1] holds blocks of size szAtom*2.
	** and so forth.
	*/
	int aiFreelist[LOGMAX+1];

	/*
	** Space for tracking which blocks are checked out and the size of each block.  One byte per block.
	*/
	u8 *aCtrl;
} mem5 = { 0 };

/*
** Access the static variable through a macro for SQLITE_OMIT_WSD
*/
#define mem5 GLOBAL(struct Mem5Global, mem5)

/*
** Assuming mem5.zPool is divided up into an array of Mem5Link structures, return a pointer to the idx-th such lik.
*/
#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))

/*
** Unlink the chunk at mem5.aPool[i] from list it is currently on.  It should be found on mem5.aiFreelist[iLogsize].
*/
static void memsys5Unlink(int i, int iLogsize)
{
	int next, prev;
	assert(i >= 0 && i < mem5.nBlock);
	assert(iLogsize>=0 && iLogsize <= LOGMAX);
	assert((mem5.aCtrl[i] & CTRL_LOGSIZE) == iLogsize);
	next = MEM5LINK(i)->next;
	prev = MEM5LINK(i)->prev;
	if (prev < 0)
		mem5.aiFreelist[iLogsize] = next;
	else
	{ MEM5LINK(prev)->next = next; }
	if (next>=0)
	{ MEM5LINK(next)->prev = prev; }
}

/*
** Link the chunk at mem5.aPool[i] so that is on the iLogsize free list.
*/
static void memsys5Link(int i, int iLogsize)
{
	int x;
	assert(system_mutex_held(mem5.mutex));
	assert(i >= 0 && i < mem5.nBlock);
	assert(iLogsize >= 0 && iLogsize <= LOGMAX );
	assert((mem5.aCtrl[i] & CTRL_LOGSIZE) == iLogsize);
	x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
	MEM5LINK(i)->prev = -1;
	if (x >= 0)
	{
		assert(x < mem5.nBlock);
		MEM5LINK(x)->prev = i;
	}
	mem5.aiFreelist[iLogsize] = i;
}

/*
** If the STATIC_MEM mutex is not already held, obtain it now. The mutex will already be held (obtained by code in malloc.c) if
** systemGlobalConfig.bMemStat is true.
*/
static void memsys5Enter(void)
{
	system_mutex_enter(mem5.mutex);
}
static void memsys5Leave(void)
{
	system_mutex_leave(mem5.mutex);
}

/*
** Return the size of an outstanding allocation, in bytes.  The size returned omits the 8-byte header overhead.  This only
** works for chunks that are currently checked out.
*/
static int memsys5Size(void *p)
{
	int iSize = 0;
	if (p)
	{
		int i = ((u8*)p-mem5.zPool) / mem5.szAtom;
		assert(i >= 0 && i < mem5.nBlock);
		iSize = mem5.szAtom * (1 << (mem5.aCtrl[i] & CTRL_LOGSIZE));
	}
	return iSize;
}

/*
** Find the first entry on the freelist iLogsize.  Unlink that
** entry and return its index. 
*/
static int memsys5UnlinkFirst(int iLogsize){
	int i;
	int iFirst;
	assert(iLogsize >= 0 && iLogsize <= LOGMAX);
	i = iFirst = mem5.aiFreelist[iLogsize];
	assert(iFirst >= 0);
	while (i > 0)
	{
		if (i < iFirst)
			iFirst = i;
		i = MEM5LINK(i)->next;
	}
	memsys5Unlink(iFirst, iLogsize);
	return iFirst;
}

/*
** Return a block of memory of at least nBytes in size. Return NULL if unable.  Return NULL if nBytes==0.
**
** The caller guarantees that nByte positive.
**
** The caller has obtained a mutex prior to invoking this routine so there is never any chance that two or more
** threads can be in this routine at the same time.
*/
static void *memsys5MallocUnsafe(int nByte)
{
	int i;           /* Index of a mem5.aPool[] slot */
	int iBin;        /* Index into mem5.aiFreelist[] */
	int iFullSz;     /* Size of allocation rounded up to power of 2 */
	int iLogsize;    /* Log2 of iFullSz/POW2_MIN */
	/* nByte must be a positive */
	assert(nByte > 0);
	/* Keep track of the maximum allocation request.  Even unfulfilled requests are counted */
	if ((u32)nByte>mem5.maxRequest)
		mem5.maxRequest = nByte;
	/* Abort if the requested allocation size is larger than the largest power of two that we can represent using 32-bit signed integers. */
	if (nByte > 0x40000000)
		return 0;
	/* Round nByte up to the next valid power of two */
	for (iFullSz = mem5.szAtom, iLogsize = 0; iFullSz < nByte; iFullSz *= 2, iLogsize++) { }
	/* Make sure mem5.aiFreelist[iLogsize] contains at least one free block.  If not, then split a block of the next larger power of
	** two in order to create a new free block of size iLogsize. */
	for (iBin = iLogsize; mem5.aiFreelist[iBin] < 0 && iBin <= LOGMAX; iBin++) { }
	if (iBin > LOGMAX)
	{
		testcase(systemGlobalConfig.xLog != 0);
		system_log(SYSTEM_NOMEM, "failed to allocate %u bytes", nByte);
		return 0;
	}
	i = memsys5UnlinkFirst(iBin);
	while (iBin > iLogsize)
	{
		int newSize;
		iBin--;
		newSize = 1 << iBin;
		mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
		memsys5Link(i+newSize, iBin);
	}
	mem5.aCtrl[i] = iLogsize;
	/* Update allocator performance statistics. */
	mem5.nAlloc++;
	mem5.totalAlloc += iFullSz;
	mem5.totalExcess += iFullSz - nByte;
	mem5.currentCount++;
	mem5.currentOut += iFullSz;
	if (mem5.maxCount < mem5.currentCount)
		mem5.maxCount = mem5.currentCount;
	if (mem5.maxOut < mem5.currentOut)
		mem5.maxOut = mem5.currentOut;
	/* Return a pointer to the allocated memory. */
	return (void*)&mem5.zPool[i*mem5.szAtom];
}

/*
** Free an outstanding memory allocation.
*/
static void memsys5FreeUnsafe(void *pOld)
{
	u32 size, iLogsize;
	int iBlock;
	/* Set iBlock to the index of the block pointed to by pOld in  the array of mem5.szAtom byte blocks pointed to by mem5.zPool. */
	iBlock = ((u8 *)pOld-mem5.zPool)/mem5.szAtom;
	/* Check that the pointer pOld points to a valid, non-free block. */
	assert(iBlock >= 0 && iBlock<mem5.nBlock);
	assert(((u8*)pOld-mem5.zPool)%mem5.szAtom == 0);
	assert((mem5.aCtrl[iBlock] & CTRL_FREE) == 0);
	//
	iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
	size = 1 << iLogsize;
	assert(iBlock+size-1 < (u32)mem5.nBlock);
	//
	mem5.aCtrl[iBlock] |= CTRL_FREE;
	mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
	assert(mem5.currentCount > 0);
	assert(mem5.currentOut >= (size*mem5.szAtom));
	mem5.currentCount--;
	mem5.currentOut -= size*mem5.szAtom;
	assert(mem5.currentOut > 0 || mem5.currentCount == 0);
	assert(mem5.currentCount > 0 || mem5.currentOut == 0);
	//
	mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
	while (ALWAYS(iLogsize<LOGMAX))
	{
		int iBuddy;
		if ((iBlock >> iLogsize) & 1)
			iBuddy = iBlock - size;
		else
			iBuddy = iBlock + size;
		assert(iBuddy >= 0);
		if ((iBuddy+(1<<iLogsize)) > mem5.nBlock)
			break;
		if (mem5.aCtrl[iBuddy] != (CTRL_FREE | iLogsize))
			break;
		memsys5Unlink(iBuddy, iLogsize);
		iLogsize++;
		if (iBuddy < iBlock)
		{
			mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
			mem5.aCtrl[iBlock] = 0;
			iBlock = iBuddy;
		}
		else
		{
			mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
			mem5.aCtrl[iBuddy] = 0;
		}
		size *= 2;
	}
	memsys5Link(iBlock, iLogsize);
}

/*
** Allocate nBytes of memory
*/
static void *memsys5Malloc(int nBytes)
{
	i64 *p = 0;
	if (nBytes > 0)
	{
		memsys5Enter();
		p = memsys5MallocUnsafe(nBytes);
		memsys5Leave();
	}
	return (void*)p; 
}

/*
** Free memory.
**
** The outer layer memory allocator prevents this routine from
** being called with pPrior==0.
*/
static void memsys5Free(void *pPrior)
{
	assert(pPrior != 0);
	memsys5Enter();
	memsys5FreeUnsafe(pPrior);
	memsys5Leave();  
}

/*
** Change the size of an existing memory allocation.
**
** The outer layer memory allocator prevents this routine from being called with pPrior==0.  
**
** nBytes is always a value obtained from a prior call to memsys5Round().  Hence nBytes is always a non-negative power
** of two.  If nBytes==0 that means that an oversize allocation (an allocation larger than 0x40000000) was requested and this
** routine should return 0 without freeing pPrior.
*/
static void *memsys5Realloc(void *pPrior, int nBytes)
{
	int nOld;
	void *p;
	assert(pPrior != 0);
	assert((nBytes & (nBytes-1)) == 0);  /* EV: R-46199-30249 */
	assert(nBytes >= 0);
	if (nBytes == 0)
		return 0;
	nOld = memsys5Size(pPrior);
	if (nBytes <= nOld)
		return pPrior;
	memsys5Enter();
	p = memsys5MallocUnsafe(nBytes);
	if (p)
	{
		memcpy(p, pPrior, nOld);
		memsys5FreeUnsafe(pPrior);
	}
	memsys5Leave();
	return p;
}

/*
** Round up a request size to the next valid allocation size.  If the allocation is too large to be handled by this allocation system,
** return 0.
**
** All allocations must be a power of two and must be expressed by a 32-bit signed integer.  Hence the largest allocation is 0x40000000
** or 1073741824 bytes.
*/
static int memsys5Roundup(int n)
{
	int iFullSz;
	if (n > 0x40000000)
		return 0;
	for (iFullSz = mem5.szAtom; iFullSz < n; iFullSz *= 2) ;
	return iFullSz;
}

/*
** Return the ceiling of the logarithm base 2 of iValue.
**
** Examples:   memsys5Log(1) -> 0
**             memsys5Log(2) -> 1
**             memsys5Log(4) -> 2
**             memsys5Log(5) -> 3
**             memsys5Log(8) -> 3
**             memsys5Log(9) -> 4
*/
static int memsys5Log(int iValue)
{
	int iLog;
	for (iLog = 0; (1 << iLog) < iValue; iLog++) ;
	return iLog;
}

/*
** Initialize the memory allocator.
**
** This routine is not threadsafe.  The caller must be holding a mutex to prevent multiple threads from entering at the same time.
*/
static int memsys5Init(void *NotUsed)
{
	int ii;            /* Loop counter */
	int nByte;         /* Number of bytes of memory available to this allocator */
	u8 *zByte;         /* Memory usable by this allocator */
	int nMinLog;       /* Log base 2 of minimum allocation size in bytes */
	int iOffset;       /* An offset into mem5.aCtrl[] */
	UNUSED_PARAMETER(NotUsed);
	/* For the purposes of this routine, disable the mutex */
	mem5.mutex = 0;
	/* The size of a Mem5Link object must be a power of two.  Verify that this is case. */
	assert((sizeof(Mem5Link) & (sizeof(Mem5Link)-1)) == 0);
	//
	nByte = systemGlobalConfig.nHeap;
	zByte = (u8*)systemGlobalConfig.pHeap;
	assert(zByte != 0);  /* sqlite3_config() does not allow otherwise */
	//
	nMinLog = memsys5Log(systemGlobalConfig.mnReq);
	mem5.szAtom = (1<<nMinLog);
	while ((int)sizeof(Mem5Link) > mem5.szAtom)
		mem5.szAtom = mem5.szAtom << 1;
	mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
	mem5.zPool = zByte;
	mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];
	for (ii = 0; ii <= LOGMAX; ii++)
		mem5.aiFreelist[ii] = -1;
	//
	iOffset = 0;
	for (ii = LOGMAX; ii >= 0; ii--)
	{
		int nAlloc = (1<<ii);
		if ((iOffset+nAlloc) <= mem5.nBlock)
		{
			mem5.aCtrl[iOffset] = ii | CTRL_FREE;
			memsys5Link(iOffset, ii);
			iOffset += nAlloc;
		}
		assert((iOffset+nAlloc) > mem5.nBlock);
	}
	/* If a mutex is required for normal operation, allocate one */
	if (systemGlobalConfig.bMemstat == 0)
		mem5.mutex = systemMutexAlloc(SYSTEM_MUTEX_STATIC_MEM);
	return SYSTEM_OK;
}

/*
** Deinitialize this module.
*/
static void memsys5Shutdown(void *NotUsed)
{
	UNUSED_PARAMETER(NotUsed);
	mem5.mutex = 0;
	return;
}

#ifdef SQLITE_TEST
/*
** Open the file indicated and write a log of all unfreed memory  allocations into that log.
*/
void systemMemsys5Dump(const char *zFilename)
{
	FILE *out;
	int i, j, n;
	int nMinLog;
	if (zFilename == 0 || zFilename[0] == 0)
		out = stdout;
	else
	{
		out = fopen(zFilename, "w");
		if (out==0)
		{
			fprintf(stderr, "** Unable to output memory debug output log: %s **\n", zFilename);
			return;
		}
	}
	memsys5Enter();
	nMinLog = memsys5Log(mem5.szAtom);
	for (i = 0; i <= LOGMAX && i + nMinLog<32; i++)
	{
		for (n = 0, j = mem5.aiFreelist[i]; j >= 0; j = MEM5LINK(j)->next, n++) ;
		fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n);
	}
	fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);
	fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);
	fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);
	fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);
	fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
	fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);
	fprintf(out, "mem5.maxCount     = %u\n", mem5.maxCount);
	fprintf(out, "mem5.maxRequest   = %u\n", mem5.maxRequest);
	memsys5Leave();
	if (out == stdout)
		fflush(stdout);
	else
		fclose(out);
}
#endif

/*
** This routine is the only routine in this file with external linkage. It returns a pointer to a static system_mem_methods
** struct populated with the memsys5 methods.
*/
const system_mem_methods *systemMemGetMemsys5(void)
{
	static const system_mem_methods memsys5Methods = {
		memsys5Malloc,
		memsys5Free,
		memsys5Realloc,
		memsys5Size,
		memsys5Roundup,
		memsys5Init,
		memsys5Shutdown,
		0 };
	return &memsys5Methods;
}

#endif /* SYSTEM_ENABLE_MEMSYS5 */
